|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
V roce 2001 Stephen Locke vyslovil hypotézu, že pro každou vyváženou množinu F obsahující 2k vadných vrcholů n-rozměrné hyperkrychle Qn, kde n ≥ k +2 a k ≥ 1, je graf Qn −F hamiltonovský. Hypotéza je stále otevřená, byť jsou již známá částečná řešení, někdy i s různými podmínkami na F. V této práci prozkoumáme hamiltonovskost grafu Qn −F, pokud množina vadných vrcholů F tvoří určitý izometrický podgraf v Qn. Pro lichou (resp. sudou) izometrickou cestu P v Qn je graf Qn − V (P) Hamiltonovsky laceabilní pro každé n ≥ 4 (resp. n ≥ 5). Přestože je znám silnější výsledek, metoda důkazu nám umožnila získat následující výsledky. Nechť C je izometrický cyklus v Qn délky dělitelné čtyřmi pro n ≥ 6. Pak je graf Qn − V (C) Hamiltonovsky laceabilní. Buď T izometrický strom v Qn s lichým počtem hran a S izometrický strom v Qm se sudým počtem hran. Pak pro každé n ≥ 4, m ≥ 5 jsou grafy Qn − T a Qm − S Hamiltonovsky laceabilní. Část důkazu je ověřena počítačem. 1
|
|
|
Hamiltonovské kružnice v hyperkrychlích s odstraněnými vrcholy
Pěgřímek, David ; Gregor, Petr (vedoucí práce) ; Dvořák, Tomáš (oponent)
V roce 2001 Stephen Locke vyslovil hypotézu, že pro každou vyváženou množinu F obsahující 2k vadných vrcholů n-rozměrné hyperkrychle Qn, kde n ≥ k +2 a k ≥ 1, je graf Qn −F hamiltonovský. Hypotéza je stále otevřená, byť jsou již známá částečná řešení, někdy i s různými podmínkami na F. V této práci prozkoumáme hamiltonovskost grafu Qn −F, pokud množina vadných vrcholů F tvoří určitý izometrický podgraf v Qn. Pro lichou (resp. sudou) izometrickou cestu P v Qn je graf Qn − V (P) Hamiltonovsky laceabilní pro každé n ≥ 4 (resp. n ≥ 5). Přestože je znám silnější výsledek, metoda důkazu nám umožnila získat následující výsledky. Nechť C je izometrický cyklus v Qn délky dělitelné čtyřmi pro n ≥ 6. Pak je graf Qn − V (C) Hamiltonovsky laceabilní. Buď T izometrický strom v Qn s lichým počtem hran a S izometrický strom v Qm se sudým počtem hran. Pak pro každé n ≥ 4, m ≥ 5 jsou grafy Qn − T a Qm − S Hamiltonovsky laceabilní. Část důkazu je ověřena počítačem. 1
|
host ::
RSS.